'''
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例一：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例二：
输入：head = [1,2]
输出：[2,1]

示例三：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
 -5000 <= Node.val <= 5000


1: 迭代法：  通过维护三个指针（前驱 prev、当前 curr、后继 next_temp），从前往后遍历链表，逐个反转节点的指向。  时间复杂度是O(N)  空间复杂度是O(1)（只用到几个变量）
2：递归法：  从链表的末尾开始，逐层反转节点的指向，将当前节点的 next 节点的 next 指向当前节点。


'''

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next  ##针对单链表 定义一个指向下一个节点的属性 就够了  不需要像双链表一样定义2个"指针"属性

#对单链表进行反转操作的核心方法
#参数 head 是待反转链表的头节点。
def reverseList(head):
    #print("head类型和head值:",type(head),head)
    # 初始化前驱节点为 None，当前节点为头节点
    prev = None
    curr = head
    ##终止条件是 curr 为False 即curr指到空节点时 也意味着单链表反转过程处理结束
    while curr:
        # 保存当前节点的下一个节点  必须在断掉原先节点之间关系前拿到这个值 不然关系断掉了 就无法获得该值了
        next_temp = curr.next
        # 反转当前节点的指向，指向前驱节点
        curr.next = prev
        # 前驱节点后移
        prev = curr
        # 当前节点后移
        curr = next_temp
    # 最终 prev 指向反转后的头节点 用pre属性是最合适的 不然反转后 next_temp、curr都是空节点 不合适
    return prev

#根据传入的参数 创建一个链表
def create_linked_list(values):
    #dummy理解为头结点，固定的节点值是0 参数传入进来的数据 都是非头结点 即绑定在dummy这一头结点的后面
    dummy = ListNode(0)
    current = dummy
    for val in values:
        #循环 一个节点一个节点创建 并依次串好
        current.next = ListNode(val)
        current = current.next  ## 以便于下一个节点的绑定
    return dummy.next  ##返回链表的非头结点的真实的第一个节点

#打印参数传进来的链表
def print_linked_list(head):
    values = []
    current = head
    while current:
        values.append(str(current.val))
        current = current.next
    return " -> ".join(values)  ## "->".join()方法 是在集合中每一组之间 插入->

# 示例 1
head1 = create_linked_list([1, 2, 3, 4, 5])
#print("反转前的数据:",print_linked_list(head1))
reversed_head1 = reverseList(head1)
print(print_linked_list(reversed_head1))  # 输出: 5 -> 4 -> 3 -> 2 -> 1

# 示例 2
head2 = create_linked_list([1, 2])
#print("反转前的数据:",print_linked_list(head2))
reversed_head2 = reverseList(head2)
print(print_linked_list(reversed_head2))  # 输出: 2 -> 1

# 示例 3
head3 = create_linked_list([])
#("反转前的数据:",print_linked_list(head3))
reversed_head3 = reverseList(head3)
print(print_linked_list(reversed_head3))  # 输出: